/**
 * 
描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示
示例:
输入: {10,6,14,4,8,12,16}
输出:From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4;
解析:
输入就是一棵二叉树，如上图，输出的时候会将这个双向链表从左到右输出，以及
从右到左输出，确保答案的正确
 */
//对二叉搜索数进行排序就是一个中序遍历
//将中序遍历的结果存入数组中，然后对数组进行遍历，添加左右节点。
//时间复杂度O(N) 空间复杂度O(N)
function Convert(pRootOfTree)
{
    // write code here
    let list=[]
    inOrder(pRootOfTree,list);
    let head=list[0];//设定头结点
    let temp=head;
    for(let i=1;i<list.length;i++){
        temp.right=list[i];
        list[i].left=temp;
        temp=list[i];
    }
    return head
}
function inOrder(root,list){
    if(root===null) return root;
    inOrder(root.left,list);
    list.push(root);
    inOrder(root.right,list);
}